# 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
#  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
#  现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
#  网格中的障碍物和空位置分别用 1 和 0 来表示。
#
#  示例 1：
# 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
# 输出：2
# 解释：3x3 网格的正中间有一个障碍物。
# 从左上角到右下角一共有 2 条不同的路径：
# 1. 向右 -> 向右 -> 向下 -> 向下
# 2. 向下 -> 向下 -> 向右 -> 向右
#
#  示例 2：
# 输入：obstacleGrid = [[0,1],[0,0]]
# 输出：1
from functools import lru_cache
from typing import List


class Solution:
    def uniquePathsWithObstacles3(self, obstacleGrid: List[List[int]]) -> int:
        """
        动态规划：
        要到达(i, j) 必须先到(i - 1, j)或者(i, j - 1)
        dp[i][j]表示从起点到(i, j)的路径数
        所以
         如果(i, j) 是可达的，即obstacleGrid[i][j] == 0 则 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
         否则(i, j) 是不可达的 则 dp[i][j] = 0
        :param obstacleGrid:
        :return:
        """
        if not obstacleGrid or obstacleGrid[0][0] or obstacleGrid[-1][-1]:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for __ in range(n)] for _ in range(m)]
        for i in range(m):  # 障碍物在第一列中，则障碍物之后的都是不可达的(初始化状态)
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break
        for j in range(n):  # 障碍物在第一行中，则障碍物之后的都是不可达的(初始化状态)
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:  # 此处有障碍物则不可达
                    dp[i][j] = 0
                else:  # 此处没有障碍物则可以先从它的左边(i, j - 1)再到该处，或者先从它的上面(i - 1, j)再到该处
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # # 可以简写成如下：
        # for i in range(m):
        #     for j in range(n):
        #         if not obstacleGrid[i][j]:  # 此处没有障碍物则可以先从它的左边(i, j - 1)再到该处，或者先从它的上面(i - 1, j)再到该处
        #             dp[i][j] = (dp[i - 1][j] if i > 0 else 0) + (dp[i][j - 1] if j > 0 else 0)
        #         if i == 0 and j == 0:
        #             dp[i][j] = 1
        return dp[-1][-1]

    def uniquePathsWithObstacles2(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or obstacleGrid[0][0] or obstacleGrid[-1][-1]:
            return 0

        @lru_cache(None)
        def fn(i: int, j: int) -> int:  # dp的递归形式
            if i == 1 and j == 1:
                return 1
            if not obstacleGrid[i - 1][j - 1]:  # 此处没有障碍物则可以先从它的左边(i, j - 1)再到该处，或者先从它的上面(i - 1, j)再到该处
                return (fn(i - 1, j) if i > 1 else 0) + (fn(i, j - 1) if j > 1 else 0)
            else:  # 此处有障碍物则不可达
                return 0
        return fn(len(obstacleGrid), len(obstacleGrid[0]))

    def uniquePathsWithObstacles1(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or obstacleGrid[0][0] or obstacleGrid[-1][-1]:
            return 0

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        return self.uniquePathsWithObstacles1(obstacleGrid)


if __name__ == "__main__":
    obstacleGrid = [[0, 0, 0],
                    [0, 1, 0],
                    [0, 0, 0]]
    obstacleGrid = [[1, 0]]
    print(Solution().uniquePathsWithObstacles(obstacleGrid))
